Shareware Grab Bag

home *** CD-ROM | disk | FTP | other *** search

/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / klp19.arc / KLP.DOC < prev next >

Wrap

Text File | 1985-12-19 | 60KB | 1,770 lines

KINETICS LINEAR PROGRAMMING SYSTEM Version 1.9, April 1984 Copyright 1984, All Rights Reserved This documentation and the associated computer software may be copied and distributed by the user provided that copies are made in entirety including copyright notices and the Kinetics Software License Agreement. A copy of this agreement is provided separately and also in Section 10 of this documentation. If you find this software useful, we trust you to send $45.00 to Kinetics Software and become a registered user. Correspondence should be addressed to: Kinetics Software 1390 Fell Street, #103 San Francisco, California 94117 CONTENTS SECTION PAGE 1. INTRODUCTION SOFTWARE.................................... 1 HARDWARE.................................... 1 OVERVIEW.................................... 2 RUNNING KLP................................. 3 2. DEFINE OPTIMIZATION........................... 4 3. CREATE MATRIX NEW DEFINITION (N).......................... 7 USING SPREADSHEET SOFTWARE (B).............. 9 SAVING THE MATRIX (S).......................12 RETRIEVING THE MATRIX (R)...................13 4. MODIFYING THE MATRIX ADJUST MATRIX SIZE, NAMES, ETC. (A).........14 CHANGE COLUMN CONTENTS (C)..................14 UPDATE ROW CONTENTS (U).....................15 5. SOLVE LP PROBLEM (L)..........................17 6. PRINT MATRIX AND RESULTS PRINT MATRIX (PP,PS,PD).....................19 PRINT RESULTS (1,2,3).......................20 GENERATE SPREADSHEET INPUT FILE.............20 7. COMMAND SUMMARY...............................21 8. GLOSSARY......................................23 9. REFERENCES ON LP..............................25 10.KINETICS SOFTWARE LICENSE AGREEMENT...........26 11.REGISTRATION OR ORDER FORM....................27 NOTE: KLP commands are indicated in parentheses. KINETICS LINEAR PROGRAMMING SYSTEM INTRODUCTION The Kinetics Linear Programming System is a computer system which those familiar with linear programming,(LP), can use to solve LP problems on a Personal Computer. In this introduction, we describe the software and hardware needed to use and compatible with KLP, provide an overview of klp's capabilities and summarize how to use KLP. SOFTWARE KLP is an integrated software system which can be used to define, solve, review and refine a linear programming problem. While no other software is necessary, KLP can be used in conjunction with VISICALC(tm), LOTUS 123(tm) and SUPERCALC2(tm). The use of KLP in conjunction with spreadsheet programs such as these is described in Section 3 of this documentation. The KLP master diskette contains 6 files: KLP.EXE - KINETICS LINEAR PROGRAMMING SYSTEM KLP.DOC - DOCUMENTATION (you are reading it) FURNFAC.MAT - FURNITURE FACTORY SAMPLE PROBLEM FURNFAC.SSI - KLP SPREADSHEET OUTPUT FURNFAC.TXT - KLP RESULTS FILE FURNFAC.DMP - KLP MATRIX PRINT FILE We suggest that you make a copy of the diskette and then put the master away in a safe place. Use the working copy for learning to use the system by going through the sample problem. All files on the disk can be typed to the screen or printer except KLP.EXE. There is no operating system on the disk. We expect that you will want to copy KLP.EXE to a working disk containing other software and files you use so that disk changes will not be necessary when going from other programs to KLP and back. HARDWARE KLP is designed to operate with minimum hardware as follows: IBM PC with one disk drive 128K of RAM memory 80 column monitor DOS 1.1 or 2.0 Printer with condensed print capability, (132 columns) Additional hardware such as a second disk drive or a hard disk can make KLP easier to use and somewhat faster, but has no affect on KLP's capacity. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 1 OVERVIEW OF KLP CAPABILITIES KLP is an integrated software system that will allow you to solve linear programing problems of considerable complexity with ease and speed. By selecting various commands, a problem can be defined and optimized, matrices can be printed or saved in files that are named as you desire and a complete set of results can be printed, saved to disk or written to a spreadsheet input file and read back in to your favorite spreadsheet for further processing, fancy reports, etc. o The original problem setup is done with this program. Alternatively, it can be done with your favorite spreadsheet program like VISICALC (tm), LOTUS 123(tm) or SUPERCALC2(tm). The rules for doing this are given in Section 3. o Once a matrix input file has been prepared, any and all manipulations of the problem can be done with KLP. Minimum and Maximum limits on rows or columns or values in the matrix itself can be changed. The number of rows and columns can be increased or decreased. The names of rows and columns may also be changed anytime. o Maximum capacity of the KLP is determined in four ways: 1. The product of rows times columns may not exceed 2000. 2. The sum of rows and columns may not exceed 120. The program will stop, print a message as to the reason and quit if either of these limits is exceeded. 3. The Adjust Matrix command is limited to 120 Column and 120 Row names. 4. The Change Columns command is limited to 60 non-zero entries in any matrix column. Limits 3 and 4 do not apply if you use a spreadsheet program to set up and modify the matrix. o In general, single letter or number responses that you make in reply to program questions or option selections do not also require a carriage return,( enter key). All other entries require a carriage return (enter key) or , in some cases, the INS key. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 2 RUNNING KLP From DOS level (A>) type: KLP KLP loads and presents a title and copyright information screen similar to the first page of this manual. Please read it. After you press any key, the main command menu is displayed as shown below: KLP COMMAND MENU DEFINE NEW MATRIX - N CHANGE COLUMNS - C RETRIEVE MATRIX - R UPDATE ROWS - U SAVE MATRIX - S ADJUST MATRIX SIZE - A PRINT MATRIX - P SOLVE LP - L RESULTS TO SCREEN - 1 QUIT - Q RESULTS TO PRINTER - 2 DUMP TO SS FILE - D RESULTS TO DISK FILE-3 BEGIN FROM SS FILE - B -------------------------------------------------------- Now you can go to work. Most of the Commands are self explanatory. However, they are summarized in Section 7. In the following Sections, we describe the process used to define an lp problem and the commands in detail. KLP will present the COMMAND screen after completing each command you select. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 3 2. - DEFINE OPTIMIZATION KLP is designed for those familiar with setting up and running LP's. If you are not, Section 9 recommends some reading material to help you. Your LP problem should be defined using a format similar to that shown below. Precise input formats are described in Section 3. The problem defined below deals with a furniture maker who must decide how many stools, chairs and tables to make in a given period of time. A B C D E F G H I J K 1 KINETICS COLUMN NAME STOOLS CHAIRS TABLES B BLOCK DOWELS LABOR 2 ITERATIONS MAX 500 500 500 100 400 320 3 ACTUAL MAXIMUM MIN 0 0 0 0 0 0 4 15 ACTIVITY 5 RED COST 6 NAME ACTIVITY MINIMUM MAXIMUM DUAL ACT 7 B BLOCK 0 0 2 3 12 -1 8 DOWELS 0 0 10 13 16 -1 9 LABOR 0 0 4 12 20 -1 10 PROFIT 0 0 -90 -120 -400 4 1.25 11 Decide on the title for the problem and the names of all the rows and columns. Write down reasonable values for the maximum and minimum values for both rows and columns. If you need a fixed value set the minimum and maximum to the same value. If, for example, a row or column really only has a minimum, a maximum must still be placed on the row or column that is just reasonably higher than any value you think could be achieved. Too large a value can increase roundoff error during the LP and cause other mathematical difficulties which may lead to no usable solution possible from the LP. Both minimums and maximums must be supplied and they must be reasonable relative to the value of the row or column in the final solution. The last row must be the objective function,( the profit or value to be optimized). Note also that KLP will always minimize the objective function, in keeping with customary LP practice. The matrix of coefficients can be viewed as equations that calculate row values from column values. For example: ROW7 = 7.0*COLUMN6 + 2.5*COLUMN7. The only equations you need are like these. You do not need to put in equations to limit either column or row values. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 4 These are direct inputs and are handled directly by KLP without taking up matrix space. This is one reason why KLP will handle much larger problems that other LP codes that allow the same matrix size, but require you to use space with row and column limit equations. In designing the matrix structure for your problem, you should try to define your equations such that non-zero values in the matrix are between 0.01 and 100.0,(plus or minus). Values less than .01 will tend to get lost as roundoff during LP iterations eats away at the number of significant digits. Numbers greater than 100. tend to cause roundoff error and loss of significant digits. The best of all possible matrices has values that are either zero or close to 1.0. You improve KLP's ability to provide fast, usable answers by paying attention to the absolute size of the numbers in your matrix. KLP calculates and prints an estimate of the roundoff error that has occurred during the LP. If this is large enough to cause the answers to be in question, KLP prints an error message, and some friendly advice! As an example of how to define an optimization, we now discuss the furniture factory example, and suggest how you may study various alternatives with KLP. Our sample problem concerns a small manufacturing firm that buys Butcher Block slabs and Dowels and makes either stools, chairs or tables from them. We want to figure out how many stools, chairs and tables we should make in a month, and how many Butcher Block slabs and Dowels we should buy given the labor force we have available. We also know that we cannot buy an unlimited number of Dowels or Butcher Blocks. Our supplies are limited to 100 Butcher Blocks and 400 Dowels per month. Each row of the LP matrix balances our purchases against usage of a particular resource. The first row balances the use of Butcher Block in the three products against purchases. The second row balances Dowels and the third Labor. The maximum and minimum values for the rows are set to zero, because the difference between purchase and use must be zero. Note that we could set the limits to a value other than zero to simulate use or buildup of inventory. The fourth row is the Profit or Objective Function. It accounts for our costs for resources and our sales income for our products. Since the LP minimizes, costs are put in as positive values, sales or incomes are put in as negative values so the LP will try to get as negative a value for the objective function as possible. The first column named STOOLS counts the number of stools we KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 5 will make in a month. Reading down the column, we see that one stool requires 2 Butcher Block slabs, 10 Dowels and 4 units of labor. The sale of one stool gives us an income of -90 dollars, negative because the LP minimizes the value of the objective function. Costs are entered as positive numbers. Similarly, the Tables column shows that we require 12 Butcher Blocks, 16 Dowels and 20 units of labor for each. Our income on sale is -400 dollars. The next three columns are to count and value our purchases. The Dowels column has a -1 just on the dowels row. Since the minimum and maximum value for the row is set to zero, the Dowels column is forced to equal the sum of the uses of dowels in stools, chairs and tables. A positive 1.25 $/dowel is put in the objective function as the cost of each one. Similarly, Butcher Blocks cost 4 each and labor 11 per unit. The limits on our purchases of Butcher Blocks and Dowels are 100 and 400. The labor limit is 320 units. The limits on production of stools, chairs and tables is set to 500 each. Much more than could be actually made. A limit is entered because KLP requires every column to have both a maximum and a minimum value. It turns out that Linear Programming is a very good method for solving these kinds of Resource Allocation problems. They are generally linear, or can be posed in terms of balance equations, (rows), with constant,(linear), coefficients. Also, in most cases, LP comes to a unique optimum solution, which makes it possible to get very consistent results when alternatives are explored. For example, we suggest that you investigate various alternatives using the sample problem as a starting point. Try changing Labor Cost, labor needed per stool or per chair, cost of materials, materials needed per chair, etc. You will readily appreciate that even such a simple example can give a manufacturer real, important insight into the effects of costs, productivity, net sales income and their interactions on the company's net profit. Linear Programming was invented many years ago,( by George B. Dantzig) to solve a resource allocation problem. Since then, ( ca 1947), numerous other uses have been found for it. LP is in everyday use for Production Scheduling, Least Cost Diet determination for animals, Transportation and Supply alternatives, Cutting Stock problems in manufacturing, and much more. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 6 SECTION 3 - DEFINE MATRIX The last section described how to define an optimization problem. This section describes how to translate your problem definition into a matrix within the KLP system. Specifically, we describe how to: o Define a matrix from scratch. o Define a matrix using a spreadsheet program. o Save a matrix. o Retrieve a previously defined matrix. Remember that KLP can be used without any spreadsheet software. Hence, if you are using KLP alone, you can skip the section on use of a spreadsheet program. DEFINING A MATRIX FROM SCRATCH A new matrix is created by using the command: N. When N is typed, KLP will ask a series of questions. Your answers to these questions will determine the title of the problem, the maximum number of iterations to be allowed, the size of the matrix and the names of the rows and columns. All values within the matrix are initially set to zero. The actual values are entered column by column using the CHANGE COLUMNS command described in Section 4. The first question is: FILENAME ? _____________ INCLUDE DISK DRIVE IDENTIFICATION (touch enter to use default: A:MATRIX.MAT) The name entered here is used when saving the matrix in future. The name should be preceeded by the disk drive designator, A: or B: for example. Except, if no designation is specified, then A: will be assumed. The name itself must be 8 or fewer characters and then should be followed by the extension .MAT. For example, the furniture factory sample problem has used the name FURNFAC.MAT. If no name is entered, the matrix filename is automatically set to A:MATRIX.MAT. Second, KLP asks: MAXIMUM ITERATIONS ? Enter a number and touch the ENTER key. The number of iterations is based on previous experience or enter about 3 times the number of columns. It is very unlikely that more than this will be required. If the maximum is reached during the LP, you will be asked whether to stop or double the limit and go on. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 7 Third, KLP asks: ENTER NUMBER OF ROWS TO ADD ( NOW = XX) ? In this case, XX will be the number of rows already in the matrix if you are changing the matrix size. XX will be zero if you are generating a new matrix. The maximum number of rows KLP can handle is 120. Answer this question with the total number of rows for a new matrix, or the additional rows if you are changing matrix size. Fourth, KLP asks: ENTER NUMBER OF COLUMNS TO ADD ( NOW = XX) ? As in the case of rows, XX will be the number of columns in the matrix if you are changing matrix size. XX will be zero if you are generating a new matrix. The maximum number of columns KLP can handle is 120. Answer this question with the total number of columns for a new matrix or the additional columns if you are changing matrix size. Next, KLP presents a screen with a number and a line for each column name. If you are changing an existing matrix, the existing names will be printed and blank lines added at the end corresponding to the number of columns you indicated you wanted to add. If this is a new matrix, all lines will be blank. Type in each name as you want it. The cursor arrow keys move the cursor as they indicate. The ENTER key moves the cursor to the next name line, and the home and end keys move you to the beginning and the end of the list respectively. Each name should contain no more than 8 characters. The number preceeding each line indicates the columns position in the matrix, from left to right. Note that existing names can be changed as well as new ones added. Existing columns also can be deleted by blanking out the name. Once you have changed or added all names as desired, accept the list by touching the INS key. Next complete the row names using the same procedure as used to complete the column names. As described in Section 2, the objective function must be the last row. When you have changed or added each row name as desired, touch INS. This accepts the row names and returns you to the command menu. Note that the matrix just defined is not automatically saved. You must now use the S command to save what you have entered in a disk file. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 8 USING A SPREADSHEET PROGRAM Skip this section if you are not using a spreadsheet program. We assume that you are experienced with whatever spreadsheet program you want to use. The example we will go through is a small application with only a few rows and columns. Our intent, after all, is not to overwork the program, but to teach you how to use it as quickly as possible. This section will explain the more mechanical aspects of what the spreadsheet must look like before you create a DIF(tm) file and actually start running KLP. The spreadsheet is divided into four areas as shown below: A B C D E F G H I J K 1 KINETICS COLUMN NAME STOOLS CHAIRS TABLES B BLOCK DOWELS LABOR 2 ITERATIONS MAX 500 500 500 100 400 320 3 ACTUAL MAXIMUM MIN 0 0 0 0 0 0 4 15 ACTIVITY 5 RED COST 6 NAME ACTIVITY MINIMUM MAXIMUM DUAL ACT 7 B BLOCK 0 0 2 3 12 -1 8 DOWELS 0 0 10 13 16 -1 9 LABOR 0 0 4 12 20 -1 10 PROFIT 0 0 -90 -120 -400 4 1.25 11 Before we delve into the details, let us deliver a caution: We strongly recommend that you use names of up to 8 characters but not longer. Many of the KLP Commands will only handle 8 characters with ease. Any modifications will require you to type the whole name correctly. The upper left area defines what is to be placed in other rows and columns and allows you to enter a title and an entry for the maximum number of LP iterations that you will allow. This area is five columns wide and six rows long. The TITLE goes in cells A1-C1. The maximum iterations go in cell B4. That's it!!. All remaining cells should be entered as shown. If you leave them out it wont hurt anything, however. All other entries are just to identify the rows below 6 and columns to the right of E. The lower left area defines the row NAMEs, the row ACTIVITY returned from the LP, the MINIMUM and MAXIMUM limit for each row and the DUAL ACTIVITY returned from the LP. You must provide a minimum and a maximum for each row except the objective function, which is always the last row. If you leave a cell blank, a zero will be assumed for the entry. A KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 9 fixed row is defined by simply setting the minimum and maximum equal. If a row has only a minimum in reality, we recommend that a maximum be placed on the row that is just reasonably above any value you expect the row could achieve. Too large a value could increase roundoff error during the LP and cause other numerical difficulties that could lead to no usable solution possible from the LP. Again, columns B and E for ACTIVITY and DUAL ACTIVITY are filled in by the LP if you use the spreadsheet input preparation option and then read the file produced back in to your spreadsheet program. The Objective Function ( the profit or value calculation that is to be optimized ) must be the last row. The upper right area is used to name all the columns and enter both minimums and maximums for each column. Rows 4 and 5 will contain the column ACTIVITY and the REDUCED COST if these are read back in from an LP generated spreadsheet input. Row 6 in this area is completely blank. As for the rows, a blank cell will be interpreted as a zero, minimums and maximums should be reasonable values, fixed columns can be defined by simply setting the minimum and maximum equal. It is best to use all columns as you define from left to right. Don't leave any blank columns. Finally, the matrix of coefficients is the lower right area. As before, a blank cell will be interpreted as a zero, so you only have to fill in values that are not zero. Each row can be viewed as an equation that calculates the row value given the column values: ROW7 = F7*COLUMNF + G7*COLUMNG + ... That's all there is to it. You do not have to worry about equations to limit column values, slack variables and so forth. All you have to do is calculate the rows from the columns. KLP takes care of the row and column limits itself, without using matrix space. Also, the cells in your matrix can be equations or formulas. Only the result of your formulas will be transmitted to the LP, so the limitation of only constant coefficients will be automatically satisfied. One caution, if cells in the matrix are actually formulas, then they will be overwritten if you read an LP generated spreadsheet input back in on top of the same part of your spreadsheet. After your matrix is ready, write it to a DIF(tm) file or convert it as required by your spreadsheet program. Be sure to include all of it from the top left area to the bottom right of the matrix proper. If you have a choice of storing by rows or columns, pick one and remember your choice. Note: VISICALC generates a DIF file directly, by row or column as you select. LOTUS 123 files are saved by columns and must be translated KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 10 from a WKS file. SUPERCALC2 files must be converted with a program from CAL files to DIF. Also, KLP will ask for the total number of spreadsheet columns and the total number of spreadsheet rows. This information is not supplied as part of the converted file. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 11 SAVE MATRIX If you want to save the matrix to a disk file, type S when the main command menu is displayed. KLP will respond: FILENAME FOR MATRIX SAVE (XX.MAT) ? XX.MAT is the name you previously entered as the desired filename for your matrix. If you touch the enter key, then the matrix will be saved under that name. You can, however, enter any other name at this time, with or without a disk drive identifier. KLP will save the file and display the message: WRITING MATRIX TO FILE. Note that the only way to change a file already saved, such as your input file, is to save a revision under the same name. KLP automatically saves its working matrix in a file named TMP.MAT on your data disk. There must be space on your data disk for this file. It is automatically erased when you use the quit Q command to end the program. If the program should for some reason end abnormally, then this file will contain your last optimization matrix. It can be retrieved for a restart under these circumstances. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 12 RETRIEVE MATRIX In order to retrieve a previously saved matrix, use the command R. When R is typed, KLP will respond: ENTER FILENAME, INCLUDE .DIF OR .MAT EXTENSION _____________ Type the disk drive prefix, the name and the .MAT extension. If the prefix is omitted, drive A: is assumed. For example, to retrieve the example problem matrix, type FURNFAC.MAT and then touch ENTER. When you touch ENTER, KLP will read the file into memory and display the message READING MATRIX FROM FILE while doing so. KLP will then return to the command menu. If KLP cannot find the named file, KLP will print the message CANNOT FIND NAMED FILE, PLEASE TRY AGAIN. KLP will then repeat the question. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 13 SECTION 4 - MODIFYING THE MATRIX The previous section described how to define a matrix, name its rows and columns, save it and retrieve it. This section describes how you change the matrix, its parameters, contents of its columns and the limits on its rows. ADJUST MATRIX SIZE The command N was used to create a new matrix and name its rows and columns. If you need to change an existing matrix, use the command A. When A is touched, KLP will respond with the same series of questions as with the N command, except KLP will not ask for a filename, it will modify the matrix in memory that has previously been retrieved or created. KLP will also provide the characteristics of the existing matrix for your reference. Please refer to Section 3 for a complete description of the command. CHANGE COLUMNS Command C allows you to change any values in the matrix a column at a time and the minimum or maximum limits on any column. When you touch C, KLP asks: COLUMN TO BE CHANGED ? _________ The name of the column you wish to change must be then entered. Upper or lower case characters in the name can be supplied. The program will automatically set upper case. The selected column is then displayed on the screen. For example, the sample problem column STOOLS will appear as: MAXIMUM 100. MINIMUM 0. B BLOCK 2 DOWELS 10 LABOR 4 PROFIT -90 MODIFYING COLUMN STOOLS , -INS- TO ACCEPT CHANGES First, the MAXIMUM and MINIMUM values for the column are shown. Second, all non-zero entries in the column are displayed, opposite their respective row names. Third, if there are any rows in the matrix that are zero for this column, then a number of blank lines are displayed corresponding to the empty rows. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 14 The cursor will be placed at the first letter of the first name. The enter key or the TAB key move you forward, field by field. The BACK-TAB (SHIFT-TAB) moves you back field by field. All cursor keys do what you think they should. The HOME key takes you to the first field. The END key takes you to the last field. If your changes get out of hand and you want to forget the whole thing, the ESC key forgets all changes to the current column. To change a value, move the cursor to the correct field using tabs, enter key, etc. Then type the new value over the old one. Any characters left from the original number are preserved. Any blank rows may be used to add a value to any row that did not originally have one. Type the row name in the first field and the desired value in the second field of each line. It is important to left-adjust the name; if you leave a blank in front of the name, KLP will not be able to recognize your entry. When all changes have been made as you desire, touch the INS key to update the matrix. KLP will then ask for the name of the next column you plan to change. Respond with its name, or touch enter to return to the command menu, The changes are permanent to the copy of the matrix held in memory. If you want to save a copy of your modified matrix, you must do so with Command S. The modify option is limited to 60 non-zero entries in a column. If you have more than this,(unlikely), the excess will not be visible on the modify screen. To change these excess row values, you can type row names over those that are visible and then enter new values as usual. Since modifications are cumulative, you can modify the same column several times to get all necessary changes made. UPDATE ROWS As with the columns of the matrix, the "left-hand-side" of every row is automatically initialized at zero. In order to change this value, use the command U. When you touch U, KLP will ask for the name of the row you plan to update. Respond as you did with the command C. KLP will then display a screen similar to that shown below: MAXIMUM 0 MINIMUM 0 STOOLS 2 CHAIRS 3 TABLES 12 B BLOCK -1 ________ ________ ________ ________ MODIFYING ROW B BLOCK , -INS- TO ACCEPT CHANGES KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 15 Changing row contents is done in exactly the same fashion as described for column changes. See the section directly above. After making all desired changes, touch the INS key to update the row. KLP will then ask for another row to change. Respond with a name, or touch enter to return to the command menu. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 16 SECTION 5 - SOLVE LP PROBLEM Once the optimization problem has been defined and expressed as a KLP matrix, the LP problem can be solved. This is done by typing the command: L. When L is typed, KLP saves a copy of the matrix in a temporary file and then solves the LP problem. You will see the LP iterations count up as the optimization proceeds. A summary of the results will be given on the lower half of the screen showing iterations, the final value of the objective function, whether the solution is Optimal or Infeasible, and an estimate of the round-off error that occurred during the solution procedure. For example, the results for the sample problem will appear as: OPTIMUM SOLUTION FOUND ITERATION 6 OBJECTIVE FUNCTION VALUE = -220.5 ROUNDOFF, RMS = 0 If all the constraints cannot be satisfied, due to an incorrectly specified problem, KLP will indicate that the solution is INFEASIBLE. Under no circumstances should such a solution be used for a useful purpose. It is very important to find the cause of the infeasibility and correct it. Only OPTIMUM solutions contain useful information about the real problem. Note that KLP calculates an estimate of the roundoff error. Roundoff is the loss of part of the result of a mathematical operation, like multiplication, due to the fixed size of number representations in computers. The extent of this roundoff is estimated by comparing the result for a row value from the LP with that calculated from the original matrix using the final column activities. The number printed is the square root of the average squared differences for all rows. If the Roundoff exceeds 2.0, KLP prints the message: ROUNDOFF LARGE, MATRIX SHOULD BE SCALED. If the Roundoff exceeds 10.0, KLP prints the message: ROUNDOFF EXCESSIVE, ANSWER PROBABLY NOT USABLE, MATRIX MUST BE SCALED! High roundoff may render a solution useless. It is usually caused by a matrix containing numbers that differ by more than four orders of magnitude. If you see this message, then you must scale your matrix. Scaling in this case means multiplying or dividing rows or columns by factors of ten so that when you are through all the numbers in the matrix are between 0.01 and 100.0 preferably. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 17 Degeneracy in LP is a rare problem that causes the solution to cycle among a small number of answers that all have very close to the same value of the objective function. It is not possible to detect easily, or cure easily. Symptoms are a large number of iterations, such as hitting the maximum iteration limit several times, and answers that are about the same with different numbers of iterations. The problem is sometimes caused by having a large number of row limits both equal to zero. In this case, it can be cured by changing some of the limits slightly. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 18 Section 6 - PRINT MATRIX AND RESULTS In this section we describe how to print the matrix or the results of an optimization to a screen, printer or disk file. PRINT MATRIX The command P is used to go to a sub-menu that directs the printing of the matrix to your screen (S), to a printer (P) or to a disk file (D). You can use the Command P and KLP will prompt you as shown below. However, you can also type PS, PP or PD to go directly to the print function without pausing. The Sub-menu is : PRINT MATRIX TO PRINTER ? (P) TO SCREEN ? (S) TO DISK FILE? (D) ENTER P,S OR D When going to a printer, KLP sets the print width to 132 and uses condensed print so that 10 matrix columns can be printed across the page. KLP will remind you to make the printer ready. If it is not ready, KLP will re-start at the above sub-menu. When going to the screen or disk file, KLP only gets four columns of the matrix across the page since 80 columns are assumed. Thus the disk file can be printed later, viewed or edited without exceeding the screen size. If you request a disk file on a write-protected disk, KLP will pause with an error message and a writeable disk must be put in the appropriate drive in order to continue. The matrix print to screen looks as below for the sample problem: SAMPLE PROBLEM COLUMN NAME - STOOLS CHAIRS TABLES B BLOCK MAXIMUM - 500.000 500.000 500.000 100.000 MINIMUM - 0.000 0.000 0.000 0.000 ROW NAME MAXIMUM MINIMUM B BLOCK 0.000 0.000 2.000 3.000 12.000 -1.000 DOWELS 0.000 0.000 10.000 14.000 16.000 0.000 LABOR 0.000 0.000 4.000 12.000 20.000 0.000 PROFIT 0.000 0.000 -90.000 -120.000 -400.000 4.000 COLUMN NAME - DOWELS LABOR MAXIMUM - 400.000 320.000 MINIMUM - 0.000 0.000 ROW NAME MAXIMUM MINIMUM B BLOCK 0.000 0.000 0.000 0.000 DOWELS 0.000 0.000 -1.000 0.000 LABOR 0.000 0.000 0.000 -1.000 PROFIT 0.000 0.000 1.250 11.000 KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 19 PRINT RESULTS TO SCREEN, PRINTER OR DISK FILE Results are printed to the screen by typing a 1, to the printer by typing a 2 or to a disk file by typing a 3. The output looks the same no matter where sent. The cautions and error messages are the same as above for printing the matrix. The printer must be ready when the command is given. The disk file must be sent to a writeable disk. The results printout appears as follows for the sample problem: KINETICS LINEAR PROGRAMMING SYSTEM 12-01-1983 10:50:00 SAMPLE PROBLEM COLUMN VARIABLES NAME ACTIVITY MINUMUM MAXIMUM RED. COST STOOLS 36.364 0.000 500.000 0.000 CHAIRS 0.000 0.000 500.000 -78.818 TABLES 2.273 0.000 500.000 0.000 B BLOCK 100.000 0.000 100.000 8.091 DOWELS 400.000 0.000 400.000 0.932 LABOR 190.909 0.000 320.000 0.000 ROW CONSTRAINTS NAME ACTIVITY MINUMUM MAXIMUM DUAL ACT. B BLOCK 0.000 0.000 0.000 -12.091 DOWELS 0.000 0.000 0.000 -2.182 LABOR 0.000 0.000 0.000 -11.000 PROFIT -1181.818 0.000 0.000 0.000 Note that if the sum of rows and columns is greater than 15, the screen cannot hold the entire output. The filename for disk file output is the same as your input file with the extension changed to TXT. RESULTS TO A SPREADSHEET INPUT FILE (DUMP TO SS FILE) The command D causes the creation of a DIF file suitable for reading back in to your spreadsheet program. The file will be written to the same disk as that containing your DIF or MAT input file. The name of the file will be the same as your input file with the extension changed to SSI. Remember that if you read this file back into your spreadsheet in the same positions as your original matrix you will wipe out any formulas or calculations in affected cells. Be careful! KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 20 SECTION 7 - COMMAND SUMMARY KINETICS LINEAR PROGRAMMING SYSTEM DEFINE NEW MATRIX - N CHANGE COLUMNS - C RETRIEVE MATRIX - R UPDATE ROW LIMITS - U SAVE MATRIX - S ADJUST MATRIX SIZE - A PRINT MATRIX - P SOLVE LP - L RESULTS TO SCREEN - 1 QUIT - Q RESULTS TO PRINTER - 2 DUMP TO SS FILE - D RESULTS TO DISK FILE-3 BEGIN FROM SS FILE - B -------------------------------------------------------- COMMAND N - DEFINE NEW MATRIX Requests filename for saving the matrix, problem title, number of iterations, number and names of rows and columns. COMMAND R - RETRIEVE MATRIX Reads a matrix file from disk into memory for solution, modification, output, etc. COMMAND S - SAVE MATRIX Writes a matrix file as specified by the user from memory to disk. COMMAND P - PRINT MATRIX Prints the matrix currently in memory to the screen, printer or a disk file. COMMAND 1,2 OR 3 - RESULTS TO SCREEN, PRINTER, DISK FILE Sends results of the most recent optimization to the screen, printer or a disk file. COMMAND C - CHANGE COLUMNS Allows change of any values in columns of the matrix and the minimum or maximum value for a column. COMMAND U - UPDATE ROWS Change the value of row limits and any values in rows. COMMAND A - ADJUST MATRIX SIZE Similar to command N, this command allows change of title, number of iterations, change in the number of rows or columns and change in the names of rows or columns. Rows or columns can also be deleted by blanking out the name. COMMAND L -SOLVE LP Perform the optimization using the current matrix in memory. Original matrix is saved prior to optimization and restored to memory from disk file after optimization. COMMAND Q - QUIT Should you for some reason tire of creation, optimization and report printing, a Q will return you to the system,(A>). KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 21 COMMAND D - DUMP TO SS FILE Writes the results of an optimization and the complete matrix to a spreadsheet input format file. Used to transfer results back to your spreadsheet program. COMMAND B - BEGIN FROM SS FILE Reads a spreadsheet output (DIF) file into memory to set up a matrix in KLP that was defined in your spreadsheet program according to the standard KLP format. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 22 SECTION 8. - GLOSSARY ACTIVITY - The value of a row or column variable in the final solution. In other words, this is the answer. COLUMN - A named variable, with upper and lower limits, corresponding to a vertical set of numbers in a matrix. Sometimes called a Vector. DUAL ACTIVITY - The effect on the objective function of a one unit change in a row limit. Also called a Shadow Price. A negative Dual Activity indicates that an increase in the maximum will improve the value of the objective function,(ie more negative). INFEASIBLE - A solution in which limits set either on columns or rows are not obeyed. This is the garbage out obtained from garbage in. This indicates that it is impossible to meet all row or column limits at the same time. The answer must not be used. ITERATIONS - The number of times that the matrix is examined for a possible improvement in the Objective Function. MATRIX - The set of numbers in vertical columns and horizontal rows that represent the problem. MAXIMUM - The upper limit set for the value of either a column or a row. MINIMUM - The lower limit set for the value of either a column or a row. OBJECTIVE FUNCTION - The row value to be optimized. In KLP the objective function is always the last, bottom row and is always minimized. OPTIMUM - A final solution that satisfies all row and column limits and has the minimum value of the objective function possible. REDUCED COST - The value of changing a column variable. Similar to a Dual Activity or Shadow Price. A positive reduced cost indicates that an increase in the column value would improve the objective function,(ie would make it more negative). ROUNDOFF - The loss of part of the result of a mathematical operation, like multiplication, due to the fixed size of number representations in computers. For example, multiplying two 5 digit numbers gives a 10 digit result. If the result is now truncated to 5 digits, some of the significance of the result is lost. In KLP, the extent of roundoff error occurring is estimated by comparing the KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 23 result for a row value from the LP with the value calculated from the original matrix. KLP prints the RMS, (root mean square ) error for all rows. ROW - A named variable, corresponding to a horizontal set of numbers in the matrix usually representing an equation that calculates a row value from column values. Sometimes called a Constraint. SCALING - The process of multiplying or dividing columns and/or rows by a factor to make the numerical magnitude of numbers in the matrix as close to 1.0 as convenient. Important in reducing the effects of roundoff on the results. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 24 SECTION 9 - REFERENCES Effective problem solving with LP takes continued use of the method and continued study and reading of the work of others in the field. We suggest the following books on the subject as representative of the literature that is both instructive and suggestive of problem areas and solution technique: Linear Programming, Vasek Chvatal, W.H. Freeman & Co. 1983. Linear Programming, S.I.Gass, McGraw-Hill, 1975. Linear Programming and Extensions, G.B. Dantzig, Princeton University Press, 1963. The bibliographies in these books will lead you further. The above list is obviously not exhaustive. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 25 SECTION 10 - KINETICS SOFTWARE LICENSE AGREEMENT 1. SOFTWARE LICENSE AGREEMENT KINETICS SOFTWARE grants and user agrees to accept a non- exclusive license to use the KLP program and associated documentation under the following terms and conditions. 2. LICENSE The KLP Program diskette may be copied and shared. Copies must be complete, as originally distributed by Kinetics Software. No charge is to be made for the program, except perhaps a nominal charge for the diskette. If you find the program useful, we trust you to send us $45.00 and become a registered user. Registered users are entitled to purchase higher capacity versions of KLP at substantial discounts and may receive help by mail from Kinetics. Correspondence from non-registered users will not be acknowledged in any way. Users who register will also receive notice of new versions, corrections and other software products of Kinetics Software. If you support us, we will make it worth your while. Be sure to include the serial number of your diskette and enclose a blank diskette when you register. If your version is not the latest, we will send you the latest free of charge. 3. COPYRIGHT COPYRIGHT 1984 KINETICS SOFTWARE. All Rights Reserved. The KLP program or any of the documentation or other materials may not be assigned, sub-licensed, distributed or otherwise transferred except as licensed above. 4. DISCLAIMER The KLP software and documentation are sold as is, and without warranty as to performance. While KINETICS SOFTWARE believes this to be a high quality product, the user must assume all risks of using the program. In no event will KINETICS SOFTWARE be liable to a user for any damages, including any lost profits or lost savings or other incidental or consequential damages arising out of the use or inability to use KLP, even if KINETICS SOFTWARE has been advised of the possibility of such damages, or for any claim by any other party. UPGRADE POLICY New releases and new versions may be released from time to time. Registered users of older versions will be entitled to upgrade at nominal cost, or to purchase higher capacity versions at substantial discount. Announcements of such new releases will be mailed to the purchasers registration address. KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 26 REGISTRATION OR ORDER FORM Send to: Kinetics Software 1390 Fell Street #103 San Francisco, Ca. 94117 ------------------------------------------------------------ Name: ____________________________________________ Address: _________________________________________ City: _________________________________________ State: _______________ Zip Code: _____________ ------------------------------------------------------------ REGISTRATION Serial Number of program : ______________________ Enclose check or money order for $45.00 and a blank diskette. ----------------------------------------------------------- ORDER ____ Latest copy of Version 1.9, Enclose $10.00. Serial number of program: ______________________ User Registration Number: ______________________ ----------------------------------------------------------- KINETICS LINEAR PROGRAMMING SYSTEM - PAGE 27